package MyDP;

import java.util.Scanner;
public class Bag {
    public static final boolean isFullPack=false;//题目是否要求恰好装满
    public static void main(String[] args) {
        //输入
        Scanner scanner=new Scanner(System.in);
        int V=scanner.nextInt();
        int N=scanner.nextInt();
        int value[]=new int[N+1];
        int weight[]=new int[N+1];
//        int num[]=new int[N+1];
        for(int i=1;i<=N;i++) {
//            num[i]=scanner.nextInt();
            weight[i]=scanner.nextInt();
            value[i]=scanner.nextInt();
        }
        //结果
        System.out.println(zeroOnePack2( N, V, weight, value));
    }

    /**
     * @param N 物品种类数
     * @param V 背包容量
     * @param weight[]物品重量
     * @param value[]物品价值
     * @return
     */
    //01背包
    public static int zeroOnePack(int N,int V,int weight[],int value[]) {
        int dp[][]=new int[N+1][V+1];//dp[i][v]表示只考虑前i个物品、背包容量为v时的最大价值
        for(int i=1;i<=N;i++) {
			/*注释掉的代码已被优化
			for(int v=1;v<=V;v++) {
				if(weight[i]>v) {
					dp[i][v]=dp[i-1][v];
				}else {
					dp[i][v]=Math.max(dp[i-1][v], dp[i-1][v-weight[i]]+value[i]);
				}
			}*/
            for(int v=weight[i];v<=V;v++) {
                dp[i][v]=Math.max(dp[i-1][v], dp[i-1][v-weight[i]]+value[i]);
            }
        }
        int maxvalue= dp[N][V];
        //输出选择的物品
        int v=V;
        String choseRes="";
        for(int i=N;i>0;i--){
            //若果dp[i][v]>dp[i-1][v],这说明第i件物品是放入背包的
            if(dp[i][v]>dp[i-1][v]){
                choseRes = i+" "+choseRes;
                v=v-weight[i];
            }
            if(v==0)
                break;
        }
        System.out.println(choseRes);
        return maxvalue;
    }
    //01背包空间压缩成On 必会
    public static int zeroOnePack2(int N,int V,int weight[],int value[]) {
        int dp[]=new int[V+1];//dp[v]背包容量为v时的最大价值
        //如果题目要求恰好装满，只需初始化dp[0]=0，dp[1~N]=负无穷。最终dp[N]<0代表无解
        if(isFullPack==true) {
            dp[0]=0;
            for(int i=1;i<=N;i++) {
                dp[i]=Integer.MIN_VALUE;
            }
        }
        for(int i=1;i<=N;i++) {
            //倒序遍历以保证dp[v-weight[i]]相当于dp[i-1][v-weight[i]]
            for(int v=V;v>=weight[i];v--) {//注意v>=weight[i]，否则越界
                dp[v]=Math.max(dp[v], dp[v-weight[i]]+value[i]);
            }
        }
        return dp[V];
    }
    //完全背包  必会
    public static int completePack(int N,int V,int weight[],int value[]) {
        int dp[]=new int[V+1];//dp[v]背包容量为v时的最大价值
        //如果题目要求恰好装满，只需初始化dp[0]=0，dp[1~N]=负无穷。最终dp[N]<0代表无解
        if(isFullPack==true) {
            dp[0]=0;
            for(int i=1;i<=N;i++) {
                dp[i]=Integer.MIN_VALUE;
            }
        }
        for(int i=1;i<=N;i++) {
            //“加选一件第 i 种物品”，正需要一个可能已选入第 i种物品的子结果 F[i,v-wi]，必须采用 v递增的顺序循环
            for(int v=weight[i];v<=V;v++) {//注意初始v=weight[i]，否则越界
                dp[v]=Math.max(dp[v], dp[v-weight[i]]+value[i]);
            }
        }
        return dp[V];
    }
    //多重背包
    public static long manyPack(int N,int V,int weight[],int value[],int num[]) {//通过80%,超时
        long dp[][]=new long[N+1][V+1];
        for(int i=1;i<=N;i++) {
            for(int j=1;j<=V;j++) {
                //如果第i件物品的重量大于背包容量j,则不装入背包
                if(weight[i] > j)
                    dp[i][j] = dp[i-1][j];
                else{
                    //考虑物品的件数限制
                    int maxNum = Math.min(num[i],j/weight[i]);
                    for(int k=0;k<=maxNum;k++){
                        dp[i][j]=Math.max(dp[i][j],Math.max(dp[i-1][j],dp[i-1][j-k*weight[i]]+k*value[i]));
                    }
                }
            }
        }
        long maxvalue= dp[N][V];
        return maxvalue;
    }
    //多重背包转01背包  必会
    public static long manyPack2(int N,int V,int weight[],int value[],int num[]) {
        int dp[]=new int[V+1];
        //如果题目要求恰好装满，只需初始化dp[0]=0，dp[1~N]=负无穷。最终dp[N]<0代表无解
        if(isFullPack==true) {
            dp[0]=0;
            for(int i=1;i<=N;i++) {
                dp[i]=Integer.MIN_VALUE;
            }
        }
        for(int i=1;i<=N;i++) {
            int numLast=Math.min(num[i], V/num[i]);
            for(int numk=1;numLast>0;numk<<=1) {
                if(numk>numLast) {
                    numk=numLast;
                }
                numLast-=numk;
                //转01背包,需要逆序。倒序遍历以保证dp[v-weight[i]]相当于dp[i-1][v-weight[i]]
                for(int v=V;v>=weight[i]*numk;v--) {
                    dp[v]=Math.max(dp[v], dp[v-weight[i]*numk]+value[i]*numk);
                }
            }
        }
        return dp[V];
    }
}